#include <stdio.h>

// 希尔排序
// 不稳定
void shellSort(int *arr,int n){
    for(int e=2;e<=n;e*=2){
        int d = n/e; 
        // 对每一组执行直接插入排序
        for(int k=0;k<d;k++){
            int temp; // 声明一个临时变量temp
            for(int i=k+d;i<n;i+=d){
                for(int j=i;j>k;j-=d){
                    if(arr[j]<arr[j-d]){
                        temp = arr[j];
                        arr[j] = arr[j-d];
                        arr[j-d] = temp;
                    }
                }
            }
        }
    }
}

int main(){
    int arr[] = {8,4,1,3,2,7,5,9,6};
    int n = sizeof(arr)/sizeof(arr[0]);
    shellSort(arr,n);
    for (int i=0;i<n;i++){
        printf("%d ",arr[i]);
    }

}